{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 17.3 The potential method"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.3-1\n",
    "\n",
    "> Suppose we have a potential function $\\Phi$ such that $\\Phi(D_i) \\ge \\Phi(D_0)$ for all $i$, but $\\Phi(D_0) \\ne 0$. Show that there exists a potential fuction $\\Phi'$ such that $\\Phi'(D_0) = 0$, $\\Phi'(D_i) \\ge 0$ for all $i \\ge 1$, and the amortized costs using $\\Phi'$ are the same as the amortized costs using $\\Phi$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Phi'(D_i) = \\Phi(D_i) - \\Phi(D_0)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.3-2\n",
    "\n",
    "> Redo Exercise 17.1-3 using a potential method of analysis."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Phi(D_i) = 2 \\cdot 2 ^ {\\lceil \\lg i \\rceil} - i$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.3-3\n",
    "\n",
    "> Consider an ordinary binary min-heap data structure with $n$ elements supporting the instructions INSERT and EXTRACT-MIN in $O(\\lg n)$ worst-case time. Give a potential function $\\Phi$ such that the amortized cost of INSERT is $O(\\lg n)$ and the amortized cost of EXTRACT-MIN is $O(1)$, and show that it works."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Phi(D_i)=$ number of elements in the heap$\\times \\lg n$.\n",
    "\n",
    "INSERT: $\\Phi(D_i) = O(\\lg n) + \\lg n = O(\\lg n)$.\n",
    "\n",
    "EXTRACT-MIN: $\\Phi(D_i) = O(\\lg n) - \\lg n = O(1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.3-4\n",
    "\n",
    "> What is the total cost of executing $n$ of the stack operations PUSH, POP, and MULTIPOP, assuming that the stack begins with $s_0$ objects and finishes with $s_n$ objects?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rll}\n",
    "\\displaystyle \\sum_{i=1}^n c_i \n",
    "&=& \\displaystyle \\sum_{i=1}^n \\hat{c_i} - \\Phi(D_n) + \\Phi(D_0) \\\\\n",
    "&=& n - s_n + s_0\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.3-5\n",
    "\n",
    "> Suppose that a counter begins at a number with $b$ 1s in its binary representation, rather than at 0. Show that the cost of performing $n$ INCREMENT operations is $O(n)$ if $n = \\Omega(b)$. (Do not assume that $b$ is constant.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rll}\n",
    "\\displaystyle \\sum_{i=1}^n c_i \n",
    "&=& \\displaystyle \\sum_{i=1}^n \\hat{c_i} - \\Phi(D_n) + \\Phi(D_0) \\\\\n",
    "&=& n - x + b \\\\\n",
    "&\\le& n - x + n \\\\\n",
    "&=& O(n)\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.3-6\n",
    "\n",
    "> Show how to implement a queue with two ordinary stacks (Exercise 10.1-6) so that the amortized cost of each ENQUEUE and each DEQUEUE operation is $O(1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Phi(D_i) = $ number of elements in the first stack."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.3-7\n",
    "\n",
    "> Design a data structure to support the following two operations for a dynamic multiset $S$ of integers, which allows duplicate values:\n",
    "\n",
    "> INSERT$(S, x)$ inserts $x$ into $S$.\n",
    "\n",
    "> DELETE-LARGER-HALF$(S)$ deletes the largest $\\lceil |S| / 2 \\rceil$ elements from $S$.\n",
    "\n",
    "> Explain how to implement this data structure so that any sequence of $m$ INSERT and DELETE-LARGER-HALF operations runs in $O(m)$ time. Your implementation should also include a way to output the elements of $S$ in $O(|S|)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An array of elements.\n",
    "\n",
    "INSERT: push the element to the back of the array.\n",
    "\n",
    "DELETE-LARGER-HALF: find the median in $O(n)$ and delete the first $\\lceil |S| / 2 \\rceil$ elements that are larger or equal to the median."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
